/*
 * @lc app=leetcode.cn id=210 lang=golang
 *
 * [210] 课程表 II
 */

// @lc code=start
func findOrder(numCourses int, prerequisites [][]int) []int {
	// 记录已学过的课程
	learned = make([]int, 0)
	// 课程的入度
	degree = make([]int, numCourses)
	// 出边数组
	edges = make([][]int, numCourses)
	// 队列（当课程的入度为零（可以直接学习）的时候入队）
	q = make([]int, 0)

	for _, val := range prerequisites {
		// 加边
		addEdge(val[1], val[0])
	}

	topsort()
	if len(learned) == numCourses {
		return learned
	}
	return []int{}
}

// 加边
func addEdge(x, y int) {
	if edges[x] == nil {
		edges[x] = make([]int, 0)
	}
	edges[x] = append(edges[x], y)
	// 课程入度+1
	degree[y]++
}

func topsort() {
	// 遍历课程的入度，为0则入队
	for i, val := range degree {
		if val == 0 {
			q = append(q, i)
		}
	}
	// 顺序出队
	for len(q) > 0 {
		// 取队头
		num := q[0]
		q = q[1:]
		// 每出队一次，代表课程已学
		learned = append(learned, num)
		// 遍历已学课程的出边，使出边的度-1
		for _, val := range edges[num] {
			degree[val]--
			// 当存在有课程入度为0，继续入队
			if degree[val] == 0 {
				q = append(q, val)
			}
		}
	}
}

var learned []int
var degree []int
var edges [][]int
var q []int

// @lc code=end

